| 翻訳と辞書 |
| Planar cover ： ウィキペディア英語版 |
Planar cover
In graph theory, a planar cover of a finite graph ''G'' is a finite covering graph of ''G'' that is itself a planar graph. Every graph that can be embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers.〔, p. 1〕
The existence of a planar cover is a minor-closed graph property,〔, Proposition 1, p. 2〕 and so can be characterized by finitely many forbidden minors, but the exact set of forbidden minors is not known. For the same reason, there exists a polynomial time algorithm for testing whether a given graph has a planar cover, but an explicit description of this algorithm is not known.
==Definition==
A ''covering map'' from one graph ''C'' to another graph ''H'' may be described by a function ''f'' from the vertices of ''C'' onto the vertices of ''H'' that, for each vertex ''v'' of ''C'', gives a bijection between the neighbors of ''v'' and the neighbors of ''f''(''v'').〔, Definition, p. 2〕 If ''H'' is a connected graph, each vertex of ''H'' must have the same number of pre-images in ''C'';〔 this number is called the ''ply'' of the map, and ''C'' is called a covering graph of ''G''. If ''C'' and ''H'' are both finite, and ''C'' is a planar graph, then ''C'' is called a planar cover of ''H''.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Planar cover」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|